FIG. 1 schematically illustrates a conventional packet switching network. The network 10 comprises a plurality of packet switches 12-A, 12-B, 12-C, 12-D. The packet switches 12-A, 12-B, 12-C, 12-D are interconnected by the transmission paths 14-A, 14-B, 14-C, 14-D, 14-E. Illustratively, the packet switches 12 are ATM (Asynchronous Transfer Mode) switches.
A plurality of user stations 16-A, 16-B, 16-C, 16-E are connected to the switches 12 by the transmission paths 18-A, 18-B, 18-C, 18-D.
An illustrative user station 16 is shown in greater detail in FIG. 2. The user station 16 includes a bus 20. Connected to the bus 20 is a CPU 22, a system memory 24, and an I/O device 26. Depending on the applications run by the station 22, the station 22 may include additional CPU's, one or more cache memory modules, and additional I/O devices. The user station 16 also includes a network interface 30 for interfacing with the network 10.
In general, a transmitting station (e.g. 16-A) and a receiving station (e.g. 16-D) communicate using a plurality of protocols which are arranged in layers. As shown in FIG. 3, the transmitting station 16-A has a protocol stack 40 comprising a plurality of protocols entities 42-1, 42-2, . . . , 42-N arranged in layers. The station 16-D has a corresponding protocol stack 50 comprised of protocol entities 52-1, 52-2, . . . , 52-N arranged in layers. The protocol entities 42 and 52 are software processes executed by a processor contained in the network interface 30 (see FIG. 2) of the stations 16-A and 16-D or executed by a CPU contained in the stations. Protocols may be executed in hardware, as well. Peer protocol entities (e.g. 42-1 and 52-1; 42-2 and 52-2; 42-N and 52-N) communicate logically using Protocol Data Units (PDU's). A PDU is the logical unit of protocol processing exchanged between peer protocol entities. Thus, as shown in FIG. 3, the protocol entity 42-1 transmits PDU's to the peer protocol entity 52-1. Similarly, the protocol entity 42-N transmits PDU's to the peer protocol entity 52-N.
Physically, communication between the transmitting station 16-A and the receiving station 16-B takes place using packets which are transmitted through the packet network 10. A packet is the unit of multiplexing in the network 10 and is the physical unit of data exchanged between user stations. The PDU's are mapped into the packets for transmission.
Layering of protocols is used to hide information to simplify processing. Typically, one or more PDU's generated in a layer K of a protocol stack are inserted into a PDU of the next lower layer K-1. Thus, a specific basic data unit (e.g., 1 byte) may belong to more than one PDU. Generally, seven layers of protocol processing are used with the highest layer being the application layer and lowest layer being the physical layer.
Several techniques can be used to increase the performance of a communication system. One technique for high performance is to process each packet as it arrives at the receiving station. The alternative is to buffer packets as they arrive and process them later. Buffering involves moving the data twice: once to the buffer and once to the processor. In Reduced Instruction Set Computer (RISC) workstation architectures, where data movement is relatively slow, immediate packet processing can increase protocol processing throughput.
The ability to process misordered data also improves communication network performance. Data misordering can be caused by message loss in the network. For example, if message 1 is received, message 2 is lost, and message 3 is received, message 2 will be retransmitted and received after message 3. Packet misordering can also occur if multipath routing is used. For example, obtaining gigabit rates on a SONET OC-3 ATM network requires using eight 155 Mbps ATM connections in parallel. Such multipath routing can result in packets leaving the network in a different order than the packets entered the network. Multipath routing also lowers latency for a single PDU if the PDU is split into packets that travel different routes. Processing of misordered data provides high application-to-application performance only if there are applications that can accept misordered data. One example of such an application is bulk data transfer. Regardless of the order in which data arrives, they can be correctly placed in the application address space. Another example is video. Although the video frames themselves must be present in the correct order, data of an individual frame can be placed in the frame buffer as they arrive without reordering. Protocol layers between the network layer and application layer also should be capable of processing misordered data.
Another technique for high performance is to reduce throughput and processing overhead by dividing each PDU so that it is transmitted in multiple packets, thus amortizing protocol control overhead across multiple packets. For example, consider two user stations which are supercomputers exchanging large blocks of data. For performance reasons, the supercomputers may prefer to do protocol processing on PDU's having a size of 64 kbyte even though the network packets may be much smaller. Similarly, in the case of an ATM network, an ATM cell is too small to carry a complete PDU. Also, interrupts can be reduced if the network interface issues interrupt commands only after complete PDU's have been received.
In short, three techniques for improving the performance of a communication network are:
(a) immediate packet processing
(b) dividing PDU's among multiple packets
(c) capability of processing misordered data
Existing data transmission methods allow simultaneously at most two of these three techniques. For example, the VMTP protocol (see e.g., D. R. Cheriton, "VMTP: A Transport Protocol for the Next Generation of Communication Systems", Prox. ACM SIGCOMM '86, pp. 406-415, Stowe, Vt., August 1986) allows packets to be processed as they arrive, even if there is misordering, but does not spread PDU overhead across multiple packets.
The IP fragmentation protocol (see e.g. J. Postel, "Internet Protocol", RFC 791, DARPA Network Working Group, September 1981) spreads the overhead of high-layer PDU's across multiple packets and is designed to handle packet misordering. However, the IP fragmentation protocol requires that PDU's be reassembled before they are processed, and thus does not allow immediate packet processing. Arriving data must be moved to a reassembly buffer until the entire data block is reassembled, then the PDU is processed as a whole. Notice that two levels of fragmentation are used in such a system: data stream to PDU's and PDU's to fragments.
The Datakit URP protocol (see e.g. A. G. Fraser and W. T. Marshall, "Data Transport in a Byte Stream Network", IEEE Journal on Selected Areas in Communications, 7(7):1020-1033, September 1989) spreads PDU overhead across multiple packets and performs immediate packet processing. However, URP assumes that packets arrive in order. On a network with misordering, packets would have to be reordered before processing, which means that for this situation immediate packet processing is no longer possible.
In view of the foregoing, it is an object of the invention to provide a data transmission technique for use in a communications network such as a packet network which overcomes the shortcomings of the prior art data transmission techniques.
More particularly, it is an object of the invention to provide a data transmission technique for use in a packet network, which enables immediate processing of arriving packets, which enables PDU's to be divided over multiple packets, and which is capable of processing misordered packets. As indicated above, prior art transmission techniques can simultaneously achieve only two of these objectives.
It is also an object of the invention to provide a data transmission technique in which a group of data (called a chunk), requiring identical processing by the protocol stack at the receiving station, is transmitted with a completely self-describing header. This header contains enough information so that the associated group of data can be processed by the protocol stack at the receiving station independently of the arrival of any other group of data.